/*
快速排序其实是一种排序执行效率很高的排序算法，它利用分治法来对待排序序列进行分治排序，
它的思想主要是通过一趟排序将待排记录分隔成独立的两部分，其中的一部分比关键字小，后面一部分比关键字大，
然后再对这前后的两部分分别采用这种方式进行排序，通过递归的运算最终达到整个序列有序。
快速排序使用了递归的概念，递归是方法内调用方法自己，一直调用下去，直到满足跳出递归的条件，否则会一直循环下去，死循环。
*/
/*
关于快速排序的原理细节，网上有两种说法
1种是交换法：
把第一个数字作为基数，同时最左边第一个数字作为left下标，最右边作为right下标。先从右向左，遇到第一个比基数小的数字后，右边下标停止，
，此时交换这两个数字。然后继续从右边往左找，直到左右下标相遇，相遇的数字和基数比较，比基数大就不动，比基数小就交换。
此时基数的位置已经确定了，不变了。原始数组被分成两个部分，继续对这两个部分使用相同的方法，递归调用方法
1种是拆补法：
也是left和right两个下标，也是先从右往左，不一样的是，把基数提出来，位置留空，右边遇到的第一个比基数小的数字，放在基数原来的的位置，
此时右边这个位置就空了，然后左边遇到的第一个比基数大的数字，放到右边空出来的位置，以此类推，直到两个下标相遇，把基数放在此时空着的位置。
http://data.biancheng.net/view/117.html
https://wiki.jikexueyuan.com/project/easy-learn-algorithm/fast-sort.html  交换的方式
https://www.cnblogs.com/MOBIN/p/4681369.html   拆补的方式
 */
package com.test.quickSort;
// 拆补法的代码实现
public class quickChaiBu {
    public static void main(String[] args) {
        int[] arr = new int[]{47,29,71,99,78,19,24,47};
        quickSort(arr,0,arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");  //不换行打印排序后的结果
        }
    }

    public static void quickSort(int[] array, int start, int end){

        if(start>=end) return;  //到某次递归的时候，如果start和end相等或start大于end了，说明此次递归只剩1个数字了，结束递归，直接返回。

        int k = array[start];  //定义基准元素，关键字

        //定义两个下标low和high，用来指向遍历比较的数字
        int low = start;  //不要直接操作start和end，后面还要用
        int high = end;

        while(low < high){

            //从右往左查找比关键字小的元素，不在while循环说明找到比关键字小的了
            while(k<= array[high] && low < high) high--;  //找不到比关键字小的就一直往左移，但不能超过low下标
            array[low] = array[high];  //把比关键字小的值放在此时左边下标指的值里

            //从左往右查找比关键字大的元素，不在while循环说明找到比关键字大的了
            while(array[low]<= k && low < high) low++;  //找不到比关键字大的就一直往右移，但不能超过high下标
            array[high] = array[low]; //把比关键字大的值放在此时右边下标指的值里
        }
        array[high] = k;  //当low和high相遇，这一遍结束了，把此时两个指针指向的同一个位置赋值成关键字的值。用low或high都可以。

        quickSort(array, start, high -1);  //左半部分递归调用方法自己，从0开始，结束的位置是上一轮的high前一位。
        quickSort(array, high+1, end);  //右半部分从上一轮的high+1开始，递归调用自己
    }
}

/*
如果想要倒序排列，把k<=array[high]改成>=,把array[low]<=k改成>=就可以了。
 */